package leet216combine

// k 是需要组合的数字个数，n是目标和。
func CombineSum3(k, n int) [][]int {
	var result [][]int
	//result = make([][]int, 0) // 注意：如果此处不make的话，最终结果会是 [][]int(nil)， 也就是切片类型的nil，而不是空的[][]int。
	var path []int
	var backtrack func(start int, left int)
	backtrack = func(start int, left int) {
		// 如果找到了k个数，并且剩余和为0，则为目标元素。
		if left == 0 && len(path) == k {
			// 这里需要拷贝一份path，因为后续的回溯会修改path。
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}
		// 递归出口有两个
		// 出口1是剩余和已经小于起始值了，说明后续都不可能了
		if left < start {
			return
		}
		if len(path) > k {
			return
		}
		if left == 0 && len(path) < k {
			// 这种情况是剩余和为0，但是数字个数没有达到k个。
			return
		}
		// 出口2是所有可用数字已经遍历完了，自动退出for循环了。
		//     因为每一次循环都伴随着path的回退(回溯)，所以也不用担心path的膨胀。
		for i := start; i <= 9; i++ {
			path = append(path, i)
			backtrack(i+1, left-i)
			path = path[:len(path)-1]
		}
	}
	backtrack(1, n)
	return result
}

func CombineSum3V2(k, n int) [][]int {
	var result [][]int
	var path []int

	var backtrack func(start int, left int)
	backtrack = func(start int, left int) {
		if len(path) == k && left == 0 {
			// 这里需要拷贝一份path，因为后续的回溯会修改path。
			pathCopy := make([]int, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}
		// 如果剩余和小于0，或者已经超过了k个数字，则直接返回。
		// 注意这里的left < 0是为了避免后续的for循环中i的值超过了9。
		// 例如：k=3, n=7，path=[1,2]，此时left=4，start=3，
		// 如果不判断left < 0，那么后续的for循环会从3开始遍历到9，path会变成[1,2,3]，然后再回溯到[1,2,4]，这样就超过了k个数字。
		if len(path) > k || left < 0 {
			return
		}
		for i := start; i <= 9; i++ {
			path = append(path, i)
			backtrack(i+1, left-i)
			path = path[:len(path)-1]
		}
	}
	backtrack(1, n)
	return result
}
